package com.tgy.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 1/15/21 6:22 PM
 *
 *  https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/
 */
public class _947_移除最多的同行或同列石头 {


    private static class Node{

        int val;
        Node parent;

        public Node(int val, Node parent) {
            this.val = val;
            this.parent = parent;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Node)) {
                return false;
            }

            Node node = (Node) o;

            return val == node.val;
        }

        @Override
        public int hashCode() {
            return val;
        }
    }


    public int removeStones(int[][] stones) {

        if (stones.length == 0) {

            return 0;
        }

        HashMap<Integer,Node> map = new HashMap<>();

        for (int i = 0; i < stones.length; i++) {
          //
            int[] stone = stones[i];

            Node node1 = map.get(stone[0]);

            if (node1 == null) {

                node1 = new Node(stone[0],null);
                map.put(stone[0],node1);
            }

            Node node2 = map.get(stone[1]);

            if (node2 == null) {
                node2 = new Node(stone[1],null);
                map.put(stone[1], node2);
            }

            union(node1,node2);
        }


        int ps = 0;
        for (Map.Entry<Integer, Node> integerNodeEntry : map.entrySet()) {

            if (integerNodeEntry.getValue().parent == null) {
                ps++;
            }
        }

        return stones.length - ps;
    }

    private Node find(Node node) {

        Node preNode = node;
        while (node != null) {

            preNode = node;
            node = node.parent;
        }

        return preNode;
    }

    private void union(Node n1, Node n2) {

        Node p1 = find(n1);
        Node p2 = find(n2);

        if (p1.equals(p2)) {

            return;
        }

        p2.parent = p1;
    }

  public static void main(String[] args) {
    //
      _947_移除最多的同行或同列石头 stones = new _947_移除最多的同行或同列石头();

//      stones.removeStones(new int[][]{{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}});
      int result = stones.removeStones(new int[][]{{0, 1}, {1, 0}});

    System.out.println(result);
  }

}
